package com.company.Tree2;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}19:48
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {5,6,2,7,8,11,-1};
        new HeapSort().heapSort(arr,arr.length);
        for (int i : arr){
            System.out.println(i+"\t");
        }
    }

    //第一步
    public void heapfiy(int[] arr,int length,int startIndex){
        if (startIndex >= length){//到了额最后一节点就没必要再走一遍了
            return;
        }
        int maxIndex = startIndex;
        //找出开始坐标的左右子树
        int left = 2*startIndex + 1;
        int right = 2*startIndex + 2;
        int temp = 0;

        if (left < length && arr[left] > arr[maxIndex]){
            maxIndex = left;
        }
        if (right < length && arr[right] > arr[maxIndex]){
            maxIndex = right;
        }
        //开始交换
        if (maxIndex != startIndex){//如果等于起始坐标 这没有发生交换 这不用进行之后的操作
            temp = arr[startIndex];
            arr[startIndex] = arr[maxIndex];
            arr[maxIndex] = temp;
            //交换完成后 便以交换后的的maxIndex坐标为起始点再进行一轮排序(就是往下走)
            heapfiy(arr,length,maxIndex);
        }
    }

    //第二步将整个堆全部走一边 主要就是所有的父节点 从下到上 从最后的一个下标值的父节点开始走
    public void heapbulid(int[] arr,int length){
        int parentIndex = (length - 1)/2;//得到最后一个节点的父节点
        for (int i = parentIndex;i >= 0;i--){
            heapfiy(arr,length,i);//因为每次都是要舍去一个父节点，所以直接可以用长度==i--来实现此效果
            //还有进行数组的最后封装
        }
    }

    public void heapSort(int[] arr,int length){
        heapbulid(arr,length);
        for (int i = length -1; i >=0; i--){
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //再次进行一次heapfiy
            heapfiy(arr,i,0);
        }
    }

}
